package com.arron.algorithm.leetcodetop100.动态规划.背包问题;

import java.util.Arrays;

/**
 *  一个可以容纳 w 重的背包，请算出背包能够装的最大价值的物品，最大价值是多少
 * 给你一个数组
 * wgt[] 表示每个物品的重量
 * vals[] 表示每个物品的价值
 */
public class 背包问题0_1 {

    int[][] mem;
    public int knapsack(int[] wgt, int[] val, int w){
        mem = new int[wgt.length][w];
        for (int[] ints : mem) {
            Arrays.fill(ints,-1);
        }
        return knapsackDFS(wgt,val,0,w);
    }

    public int knapsackDFS(int[] wgt, int[] val, int start,int w){

        if (w<0){
            return 0;
        }


        if (start>=wgt.length){
            return 0;
        }


        //这次选择装入背包 的价值
        int chooseVal = knapsackDFS(wgt,val,start+1,w-wgt[start]);
        //这次不选择装入背包
        int noChooseVal = knapsackDFS(wgt,val,start+1,w);
        return Math.max(chooseVal,noChooseVal);

    }

    public int knapsackDFS_mem(int[] wgt, int[] val, int start,int w){

        if (w<0){
            return 0;
        }


        if (start>=wgt.length){
            return 0;
        }
        if (mem[start][w] != -1){
            return mem[start][w];
        }


        //这次选择装入背包 的价值
        int chooseVal = knapsackDFS(wgt,val,start+1,w-wgt[start]);
        //这次不选择装入背包
        int noChooseVal = knapsackDFS(wgt,val,start+1,w);
        mem[start][w] = Math.max(chooseVal,noChooseVal);
        return mem[start][w];
    }




    public int knapsackDynamic(int[] wgt, int[] val,int w){

        //定义dp ，dp[i][j] 表示 选择前i 个书包 重量为j的最大价值
        int[][] dp = new int[wgt.length+1][w+1];

        //base case
        // dp[0][0...j] =0 , dp[0...i][0] =0

        for (int i = 1; i <=wgt.length ; i++) {
            for (int j = 1; j <= w ; j++) {

                if (j-wgt[i-1] <0){
                    //小于0时，背包装不了了，此时的最大价值继承之前的
                    dp[i][j] = dp[i-1][j];
                }else {
                    //选择 不装入背包和装入背包和的最大价值那一个
                    dp[i][j] = Math.max(dp[i-1][j],val[i-1]+dp[i-1][j-wgt[i-1]]);
                }
            }

        }
        return dp[wgt.length][w];

    }



}
